package com.example.jianzhioffer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by Quincy on 2018/10/7.
 * 把二叉树打印成多行
 * 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 */
public class PrintNode2Row {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
        if (pRoot == null)
            return arrs;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(pRoot);
        int last = q.size(), count = 0;
        while (!q.isEmpty()){
            count = 0;
            last = q.size();
            ArrayList<Integer> arr = new ArrayList<>();
            while (count < last){
                TreeNode t = q.poll();
                count++;
                arr.add(t.val);
                if (t.left != null)
                    q.add(t.left);
                if (t.right != null)
                    q.add(t.right);
            }
            arrs.add(arr);
        }
        return arrs;
    }

    /**
     * 递归
     * */
    ArrayList<ArrayList<Integer> > Print2(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }

    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
        if(root == null) return;
        if(depth > list.size())
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);

        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }

}
